a. Field of the Invention
This invention relates generally to computer architecture and more specifically to modes of addressing in random access memories.
b. Related Art
In today's computer architectures, translation between virtual and real (physical) memory is generally done via page tables, which have, for each virtual page, its corresponding location within real memory. Access to a location within a virtual page, given by an offset from the beginning of the page, can be performed by fetching the contents of the real memory address of the page, as modified by the same offset.
An emerging development in computer architecture is the use of data compression in main or random access memory. Here, each virtual page, after compression, can be stored in some number of smaller storage blocks of either uniform or variable size with the number being dependent on the effectiveness of the compression means on this particular page. For example, virtual pages of 4 k bytes might be stored, after compression, in some number of blocks of 256 byte size. The virtual page can then be retrieved by providing to the memory controller the identities of the corresponding blocks.
As noted above, it is often desirable to access, not the entire page, but rather some location within the page, specified by the offset from the page start. In general, this may require that the entire page be first decompressed. An exception to this is when the page contents are divided into two or more lines, for example four 1 k lines per 4 k page, and the lines compressed and decompressed individually. This latter form of organization is desirable in that the amount of work required to access a particular location within a page is reduced, and with it the required latency or delay. In this latter form of organization addressing is provided to the beginning of each line, which in general may start anywhere within any of the blocks within which the compressed line is stored. This is illustrated in FIG. 1.
In FIG. 1, the page 1 consists of four lines, 1a, 1b, 1c, 1d, which are stored in compressed form 1a', 1b', 1c', 1d' in three fixed size blocks 2a, 2b, 2c. Pointers to locations within these blocks are provided (by way of a table, not shown) in order to enable immediate access to the beginning of any desired line. This is awkward, however, as four such pointers need be provided to the addressing mechanism. In contrast, most of today's machines require only one such pointer, corresponding to the page frame. Moreover, in the latter form of organization the four pointers need to be long enough to specify the location within the block, not just the block, within which the desired line resides. This increases the number of bits per pointer.